package leetcode;


import common.Node;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 克隆图
 */
public class LeetCode133 {
    public Node cloneGraph(Node node) {
        if (node == null) return node;
        Map<Node, Node> map = new HashMap();
        Stack<Node> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            Node nNode = new Node(cur.val);
            map.put(cur, nNode);
            for (Node n : cur.neighbors) {
                if (!map.containsKey(n)) stack.push(n);
            }
        }
        for (Node n : map.keySet()) {
            Node nNode = map.get(n);
            for (Node nei : n.neighbors) {
                nNode.neighbors.add(map.get(nei));
            }
        }
        return map.get(node);
    }
}